/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/11
 */
package CodingTest.AC20190410;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * leetcode - 90
 * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

 说明：解集不能包含重复的子集。

 示例:

 输入: [1,2,2]
 输出:
 [
 [2],
 [1],
 [1,2,2],
 [2,2],
 [1,2],
 []
 ]
 */
public class subsetWithDup {
    //方法一：
    public List<List<Integer>> subsetWithDup(int[] nums){
        Arrays.sort(nums);
        HashSet<List<Integer>> result = new HashSet<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        List<List<Integer>> result1 = new ArrayList<List<Integer>>();
        helper(nums,result,list,0);
        for(List<Integer> e : result){
            result1.add(e);
        }
        return result1;
    }
    public void helper(int[] nums,HashSet<List<Integer>> result,List<Integer> list,int start){
        result.add(new ArrayList<Integer>(list));
        for(int i =start;i<nums.length;i++){
            list.add(nums[i]);
            helper(nums,result,list,i+1);
            list.remove(list.size()-1);

        }
    }
    //方法二：
    public List<List<Integer>> subsetWithDup2(int[] nums){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);
        helper(nums,result,list,0);
        return result;
    }
    public void helper(int[] nums,List<List<Integer>> result,List<Integer> list,int start){
        result.add(new ArrayList<>(list));
        for(int i = start;i<nums.length;i++){
            if(i>start && nums[i] == nums[i-1]) continue;
            list.add(nums[i]);
            helper(nums,result,list,i+1);
            list.remove(list.size()-1);
        }
    }





    public static void main(String[] args) {
        subsetWithDup sb = new subsetWithDup();
        int [] nums = {4,4,4,1,4};
        System.out.println(sb.subsetWithDup2(nums));
    }
}
